SCCPC2026 G 禁忌教典的消失咒文题解

发表于 2026-06-22 分类于题解

我们要删除一个非空连续区间，然后把剩下的两段拼起来。麻烦的地方在于，拼接以后右半段的符号可能会改变。

定义交替前缀和

$$
P_i=\sum_{t=1}^{i}(-1)^{t+1}a_t,\qquad P_0=0.
$$

设删除区间是 $[l,r]$，令

$$
i=l-1,\qquad j=r.
$$

也就是说，我们要统计 $0\le i<j\le n$ 的二元组。

删除 $a_{i+1},\ldots,a_j$ 后，前半段 $a_1,\ldots,a_i$ 的符号不变；后半段 $a_{j+1},\ldots,a_n$ 是否翻转，取决于删除长度 $j-i$ 的奇偶性。

如果 $j-i$ 是偶数，右半段的符号不变，删除后的能量为

$$
P_i+P_n-P_j.
$$

要求它等于 $k$，即

$$
P_j-P_i=P_n-k.
$$

这时 $i,j$ 同奇偶。

如果 $j-i$ 是奇数，右半段的符号会翻转，删除后的能量为

$$
P_i+P_j-P_n.
$$

要求它等于 $k$，即

$$
P_i+P_j=P_n+k.
$$

这时 $i,j$ 异奇偶。

于是可以从左到右枚举右端点 $j$，用两个哈希表维护此前出现过的 $P_i$：一个存偶数下标，一个存奇数下标。

对于当前 $j$：

把两类方案数加入答案后，再把当前的 $P_j$ 放入对应奇偶性的哈希表。

注意删除区间要求非空，而我们始终枚举 $i<j$，所以不会把空区间算进去。

使用哈希表时，时间复杂度为期望 $O(n)$，空间复杂度为 $O(n)$。如果使用平衡树或 map，时间复杂度为 $O(n\log n)$。